package 动态规划.打家劫舍;

import 动态规划.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * author: shalock.lin
 * date: 2022/11/11
 * describe: 打家劫舍系列题
 */
public class Main {

    public static void main(String[] args) {
        System.out.println(rob2(new int []{1,2,3}));
    }


    /**
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/house-robber
     *
     * 1. dp[i] 为偷到第i家时所获得的最高金额
     * 2. dp[i]=max(nums[i-1],dp[i-2]+nums[i])
     * 3. dp[1] = nums[1] dp[2] = max(nums[1], nums[2])
     * 4. 从1遍历到length
     *
     * 注意：第二家的dp值初始化是 max(nums[1], nums[2]) 而不是nums[2]
     */
    public static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int length = nums.length;

        int lastlast = nums[0], last = Math.max(nums[0], nums[1]), result = last;
        for (int i =2; i < length; i++) {
            result = Math.max(last, nums[i]+lastlast);
            lastlast = last;
            last = result;
        }
        return result;
    }

    /**
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/house-robber-ii
     *
     * 1. dp[i] 为偷到第i家时所获得的最高金额
     * 2. dp[i]=max(nums[i-1],dp[i-2]+nums[i])
     * 3. dp[1] = nums[1] dp[2] = max(nums[1], nums[2])
     * 4. 从1遍历到length
     *
     * 思路：相比第一种多了个条件，就是第一家和最后一家不能同时偷
     * 因此可以拆分为两种情况，第一种就是偷第一家(因此不能偷最后一家)，第二种就是不偷第一家。取两者最大值
     *
     * 注意：第一种 第二家的初始化为第一家的金额， 第二种情况 第一家的初始化为0
     */
    public static int rob2(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int length = nums.length;

        int lastlast = nums[0], last = nums[0], result1 = last;
        for (int i = 2; i < length-1; i++) {
            result1 = Math.max(last, lastlast+nums[i]);
            lastlast = last;
            last = result1;
        }

        lastlast = 0;
        last = nums[1];
        int result2 = last;
        for (int i = 2; i < length; i++) {
            result2 = Math.max(last, lastlast+nums[i]);
            lastlast = last;
            last = result2;
        }
        return Math.max(result1, result2);
    }

    /**
     * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
     *
     * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
     *
     * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/house-robber-iii
     *
     * 1. dp[TreeNode] 以当前节点为父节点的树所能盗到最多的金额
     *
     * 注意：遍历树/图的方式主要有深度/广度优先
     */

    static Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    static Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

    public static int rob3(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public static void dfs(TreeNode node) {
        if (node == null) return;

        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left,0)+ g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.right,0), g.getOrDefault(node.left,0))+Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }
}
